#pragma once


#include<iostream>
#include<string>
#include<vector>
#include<utility>

using namespace std;

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	HashNode(const T& data)
		:_data(data)
		,_next(nullptr)
	{}
};

template<class T>
struct defaultHashfunc
{
	size_t operator()(const T& data)
	{
		return (size_t)data;
	}
};

template<>
struct defaultHashfunc<string>
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (auto& ch : str)
		{
			hash *= 131;

			hash += ch;
		}
		return hash;
	}
};


template<class K, class T, class KeyofT, class HashFunc>
class HashTable;

template<class K,class T,class Ptr,class Ref,class KeyofT, class HashFunc>
struct HashIterator
{
	typedef HashNode<T> Node;
	typedef HashIterator<K, T, Ptr, Ref ,KeyofT, HashFunc> Self;
	typedef HashIterator<K, T, T*, T&, KeyofT, HashFunc> iterator;

	Node* _node;
	const HashTable<K, T, KeyofT, HashFunc>* _pht;

	HashIterator(Node* node, HashTable<K, T, KeyofT, HashFunc>* pht)
		:_node(node)
		,_pht(pht)
	{}

	HashIterator(const iterator& it)
		:_node(it._node)
		,_pht(it._pht)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &_node->_data;
	}

	Self& operator++()
	{
		if (_node->_next)
		{
			_node = _node->_next;
		}
		else
		{
			KeyofT kot;
			HashFunc hf;
			size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
			++hashi;
			while (hashi < _pht->_table.size())
			{
				if (_pht->_table[hashi])
				{
					_node = _pht->_table[hashi];
					return *this;
				}
				else
				{
					++hashi;
				}
			}
			_node = nullptr;
		}
		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)
	{
		return _node->_data == s._node;
	}
};


template<class K,class T,class KeyofT,class HashFunc = defaultHashfunc<K>>
class HashTable
{
	template<class K, class T, class Ptr,class Ref,class KeyofT, class HashFunc>
	friend struct HashIterator;
public:

	typedef HashNode<T> Node;
	typedef HashIterator<K, T, T*, T&, KeyofT, HashFunc> iterator;
	typedef HashIterator<K, T,const T*,const T&,KeyofT, HashFunc> const_iterator;

	iterator begin()
	{ 
		for (int i = 0; i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				if (cur)
		
				{
					return iterator(cur, this);
				}
			}
		}
		return iterator(nullptr, this);
	}
	iterator end()
	{
		return iterator(nullptr, this);
	}

	const_iterator begin()const 
	{
		int i = 0;
		for (i = 0; i < _table.size(); ++i)
		{
			Node* cur = _table[i];
			while (cur)
			{
				if (cur)

				{
					return const_iterator(cur, this);
				}
			}
		}
		return const_iterator(nullptr, this);
	}

	const_iterator end()const 
	{
		return const_iterator(nullptr, this);
	}

	HashTable()
	{
		_table.resize(10,nullptr);
	}
	~HashTable()
	{
		for (int i = 0; i < _table.size(); i++)
		{
			Node*  cur  = _table[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_table[i] = nullptr;
		}
	}
	pair<iterator,bool> insert(const T& data)
	{
		KeyofT kot;
		HashFunc hf;
		
		iterator it = Find(kot(data));
		if (it != end())
		{
			return make_pair(it,false);
		}

		if (_n == _table.size())
		{
			size_t newsize = _table.size() * 2;
			vector<Node*> newtable;
			newtable.resize(newsize,nullptr);
			for (int i = 0; i < _table.size() ;i++)
			{
				HashFunc hf;
				size_t hashi = 0;

				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					hashi = hf(kot(cur->_data)) % newtable.size();
					cur->_next = newtable[hashi];
					newtable[hashi] = cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
			_table.swap(newtable);

		}
		size_t hashi = hf(kot(data)) % _table.size();
		Node* newnode = new Node(data);
		newnode->_next = _table[hashi];
		_table[hashi] = newnode;
		++_n;
		return make_pair(iterator(newnode,this),true);
 	}

	iterator Find(const K& key)
	{
		HashFunc hf;
		KeyofT kot;
		size_t hashi = hf(key) % _table.size();
		Node* cur = _table[hashi];
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				return iterator(cur,this);
			}
			cur = cur->_next;
		}
		return iterator(nullptr, this);
	}

	bool Erase(const K& key)
	{
		HashFunc hf;
		KeyofT kot;
		size_t hashi = hf(kot(key)) % _table.szie();
		Node* cur = _table[hashi];
		Node* prev = nullptr;
		while (cur)
		{
			if (kot(cur->_data) == key)
			{
				if (prev == nullptr)
				{
					_table[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}

				delete cur;
				--_n;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}

	void Print()
	{
		KeyofT kot;
		for (int i = 0;i < _table.size(); i++)
		{
			Node* cur = _table[i];
			while (cur)
			{
				cout << kot(cur->_data);
				cur = cur->_next;
			}

		}
		cout << endl;
	}
private:
	vector<Node*> _table;
	size_t _n = 0;
};

